//
//  itertools.h
//  cobalt
//
//  Created by Nicolas Godbout on 2013-09-04.
//  Copyright (c) 2013 Nicolas Godbout. All rights reserved.
//

#ifndef cobalt_itertools_h
#define cobalt_itertools_h


#include <iterator>
#include <type_traits>

/** Encapsulates a C++ Iterator into an object adhering to the CobaltIterator concept **/
template<class It>
class Range {
public:
    typedef typename It::value_type     value_type;
    
    Range(std::pair<It,It>&& pair)
    : pair(std::forward<std::pair<It,It>>(pair)) {}
    
    operator bool() const {
        return pair.first != pair.second;
    }
    
    value_type
    operator*() {
        return *pair.first;
    }
    
    Range&
    operator++() {
        ++pair.first;
        return *this;
    }
    
    Range&
    toEnd() {
        pair.first = pair.second;
        return *this;
    }
    
public:
    std::pair<It,It>    pair;
};




/** This is NOT a proper C++ iterator, not EqualityComparable, not CopyConstructible
    and not CopyAssignable.
    Instead, an operator bool() is defined to check for end-of-enum.
 **/

// class It1 and It2 must satisfy the requirements of CobaltIterator and OrderedIterator
template<class CoIt1, class CoIt2,class Compare>
class Intersect {
public:
    typedef typename CoIt1::value_type     value_type;
    static_assert(std::is_same<value_type, typename CoIt2::value_type>::value,"Template arguments to Intersect<> must produce the same value type.");
    
    Intersect(CoIt1 const& l, CoIt2 const& r)
    : left(l), right(r) {
        if ( !left ) right.toEnd();
        if ( !right ) left.toEnd();
        if ( Compare()(*left, *right) || Compare()(*right, *left) )
            operator++();
    }
    
    value_type
    operator*() {
        if ( !right ) return *left;
        if ( !left )  return *right;
        if ( Compare()(*right, *left) )
            return *right;
        else
            return *left;
    }
    
    Intersect&
    operator++();
    
    Intersect&
    toEnd() {
        left.toEnd();
        right.toEnd();
        return *this;
    }
    
    operator
    bool() const {
        return left || right;
    }
    
private:
    CoIt1  left;
    CoIt2  right;
};

template<class CoIt1,class CoIt2,class Compare>
Intersect<CoIt1,CoIt2,Compare>&
Intersect<CoIt1,CoIt2,Compare>::operator++() {
    if ( !left || !(++left) ) {
        right.toEnd();
        return *this;
    }
    // ## CHECK if this test is superfluous
    if ( !right ) {
        left.toEnd();
        return *this;
    }
    while ( true ) {
        if ( Compare()(*left, *right) ) {
            ++left;
            if ( !left ) {
                right.toEnd();
                return *this;
            } else
                continue;
        } else if ( Compare()(*right, *left) ) {
            ++right;
            if ( !right ) {
                left.toEnd();
                return *this;
            } else
                continue;
        } else
            return *this;
    }
}


template<class It>
class Merge {
public:
    typedef typename It::value_type     value_type;
    
    Merge(std::pair<It,It> const& left, std::pair<It,It> const& right)
    : left(left), right(right) {}
    
    value_type
    operator*() {
        if ( !right.first ) return *left.first;
        if ( !left.first )  return *right.first;
        if ( *right.first < *left.first )
            return *right.first;
        else
            return *left.first;
    }
    
    Merge&
    operator++() {
        if ( !right.first )
            ++left.first;
        else if ( !left.first )
            ++right.first;
        else if ( *right.first < *left.first )
            ++right.first;
        else
            ++left.first;
        return *this;
    }
    
    operator
    bool() const {
        return left.first != left.second && right.first != right.second;
    }
    
private:
    std::pair<It,It>    left;
    std::pair<It,It>    right;
};

#endif
